from contextlib import contextmanager
from collections import deque
from sys import stdout
from os import path
import sys, random

# ---------------------------------------------------------
# Small classes that don't justify separate files ---------
class Namespace(dict):
    """Utility class that works as a dict or as a regular object. Users can add string keys 
    through attribute assignment, and/or regular subscripting. The following are equivalent:
        ns.x = 3
        ns["x"] = 3
    For non-string keys subscripting is required, as the attribute-like notation only allows 
    string keys with the usual character limitations (no #$!? etc. allowed)."""
    __getattr__ = dict.__getitem__
    __setattr__ = dict.__setitem__
    __delattr__ = dict.__delitem__
    
    @property
    def __dict__(self):
        return self
        
    def __getstate__(self):
        return dict(self)
        
    def __setstate__(self, dictionary):
        self.update(dictionary)
        
    def copy(self):
        return self.__class__(self)
    
class Singleton(object):
    """This class implements a singleton constructor. To make a class singleton (i.e. have only 
    one existing instance), just subclass the Singleton class, and voila!"""
    def __new__(cls, *args, **kwargs):
        if not hasattr(cls, "__singleton__"):
            setattr(cls, "__singleton__", object.__new__(cls, *args, **kwargs))
        return getattr(cls, "__singleton__")
        
class Undefined(Singleton):
    """A singleton class that can be useful for functions or methods where you can't find a good 
    default value to signal a missing argument, e.g. where None can be interpreted as data."""
    pass
    
class Switch(object):
    """Something that can be turned on, off, and toggled between states."""
    def __init__(self, enabled=True):
        self.__enabled = False
        self.enabled = enabled
        
    def __repr__(self):
        state = "enabled" if self.__enabled else "disabled"
        return "<%s(%s) at 0x%08x>" % (self.__class__.__name__, state, id(self))
        
    def enable(self):
        """Redefine in subclasses (but call the superclass's method)."""
        self.__enabled = True
        
    def disable(self):
        """Redefine in subclasses (but call the superclass's method)."""
        self.__enabled = False
        
    def toggle(self):
        self.enabled = not self.__enabled
        
    @property
    def enabled(self):
        return self.__enabled
        
    @enabled.setter
    def enabled(self, new_enabled):
        if not self.__enabled and new_enabled:
            self.enable()
        elif self.__enabled and not new_enabled:
            self.disable()
            
class Clock(object):
    """Clock object for CPU tracking. To track the CPU time of a function just call it in a 
    tracking() context block, like:
        tracker = Clock()
        with tracker.tracking():
            do_stuff()
        print "Elapsed CPU time:", tracker.total()
    """
    def __init__(self, start=False):
        self._start = None
        self._cpu = 0.0
        self._tracks = 0
        if start:
            self.start()
            
    def __repr__(self):
        return "<%s(%fs [%d tracks]) @ 0x%08x>" % (self.__class__.__name__, self.total, 
                                                   self._tracks, id(self))
        
    @property
    def active(self):
        return self._tracks > 0
        
    @property
    def total(self):
        if not self._tracks:
            return self._cpu
        else:
            return self._cpu + (clock() - self._start)
            
    def clear(self, force=False):
        if not force and self._tracks > 0:
            raise ValueError("cannot reset CPU tracker - active track(s) remaining")
        self._start = None
        self._cpu = 0.0
        self._tracks = 0
        
    def start(self):
        if self._tracks == 0:
            self._start = clock()
        self._tracks += 1
        
    def stop(self):
        if self._tracks == 0:
            raise ValueError("cannot stop CPU tracker - no active track(s) remaining")
        self._tracks -= 1
        if self._tracks == 0:
            self._cpu += clock() - self._start
            self._start = None
            
    @contextmanager
    def tracking(self):
        self.start()
        yield
        self.stop()
        
class Cache(object):
    """A general-purpose cache which can be used to store data like a dictionary, but has a 
    cleanup() procedure which is called whenever its contents reach the maximum size limit."""
    def __init__(self, size=5000, reduce_to=0.75, protected=()):
        self.size = size
        self.reduce_to = reduce_to
        self.content = dict()
        self.order = deque()
        self.protected = set(protected)
        
    def __len__(self):
        return len(self.content)
        
    def __contains__(self, key):
        return key in self.content
        
    def __getitem__(self, key):
        return self.content[key]
        
    def __setitem__(self, key, value):
        if key in self.content:
            self.order.remove(key)
        self.content[key] = value
        self.order.append(key)
        if len(self.content) > self.size:
            self.cleanup()
            
    def __delitem__(self, key):
        del self.content[key]
        self.order.remove(key)
        self.protected.discard(key)
        
    def cleanup(self, reduce_to=None, protected=None):
        if reduce_to is None:
            reduce_to = self.reduce_to
        if protected is None:
            protected = self.protected
        else:
            protected = self.protected.union(set(protected))
        temp = deque()
        target_size = int(reduce_to * self.size)
        while len(self.content) > target_size:
            item = self.order.popleft()
            if item in self.content:
                if item in protected: 
                    temp.appendleft(item)
                else:
                    del self.content[item]
        self.order.extendleft(temp)
        
    def get(self, key, default_value=None):
        return self.content.get(key, default_value)
        
    def pop(self, key):
        value = self.content.pop(key)
        self.order.remove(key)
        self.protected.discard(key)
        return value
        
    def update(self, **data):
        for key, value in data.iteritems():
            self[key] = value
            
class PersistHelper(object):
    """This class helps the load/save operations of files with an optional extension into a 
    specified directory. The directory path and file extension are automatically added to the 
    filenames supplied to the load() and save() methods."""
    load_fnc  = None
    save_fnc  = None
    directory = "."
    extension = None
    
    def __init__(self, load_fnc=None, save_fnc=None, directory=None, extension=None):
        if  load_fnc is not None: self.load_fnc  = load_fnc
        if  save_fnc is not None: self.save_fnc  = save_fnc
        if directory is not None: self.directory = directory
        if extension is not None: self.extension = extension
        
    def load(self, infile, *args, **kwargs):
        full_path = path.abspath(path.join(self.directory, infile))
        if self.extension is not None and not full_path.endswith(self.extension):
            full_path += self.extension
        return self.load_fnc(full_path, *args, **kwargs)
        
    def save(self, obj, outfile, *args, **kwargs):
        full_path = path.abspath(path.join(self.directory, outfile))
        if self.extension is not None and not full_path.endswith(self.extension):
            full_path += self.extension
        self.save_fnc(obj, full_path, *args, **kwargs)
        
class FunctionProxy(object):
    """This class allows the creation of function/method proxy classes. An example of its usage 
    can be found in the Component class of khronos.des."""
    def __init__(self, target):
        self.target = target
        
    @classmethod
    def include(cls, name_or_fnc):
        if isinstance(name_or_fnc, str):
            def decorator(fnc):
                def new_fnc(self, *args, **kwargs):
                    return fnc(self.target, *args, **kwargs)
                new_fnc.__name__ = name_or_fnc
                new_fnc.__doc__ = fnc.__doc__
                setattr(cls, new_fnc.__name__, new_fnc)
                return fnc
            return decorator
        else:
            decorator = cls.include(name_or_fnc.__name__) 
            return decorator(name_or_fnc)
            
class treedict(object):
    """A class with only static methods (aka functions) which are related to the creation 
    of tree-like dictionary structures."""
    def __new__(cls, iterable):
        D = dict()
        treedict.update(D, iterable)
        return D
        
    @staticmethod
    def update(D, iterable):
        for path in iterable:
            treedict.set(D, *path)
            
    @staticmethod
    def get(D, *path):
        for elem in path:
            D = D[elem]
        return D
        
    @staticmethod
    def has(D, *path):
        try:
            treedict.get(D, *path)
        except KeyError:
            return False
        else:
            return True
            
    @staticmethod
    def set(D, *path):
        # go down path as long as possible
        iterator = iter(path[:-2])
        for elem in iterator:
            try:
                next_D = D[elem]
            except KeyError:
                next_D = D[elem] = dict()
                D = next_D
                break
            D = next_D
        # build missing part of path (and keep going down)
        for elem in iterator:
            next_D = D[elem] = dict()
            D = next_D
        # and finally make the assignment
        D[path[-2]] = path[-1]
        return path[-1]
        
    @staticmethod
    def pop(D, *path):
        D = treedict.get(D, *path[:-1])
        return D.pop(path[-1])
        
    @staticmethod
    def pop_path(D, *path):
        """Same as treedict.pop(), but deletes the dictionaries in the path if they become empty 
        after the removal of the item."""
        dicts = []
        for elem in path[:-1]:
            dicts.append(D)
            D = D[elem]
        value = D.pop(path[-1])
        for elem in reversed(path[:-1]):
            D = dicts.pop()
            if len(D[elem]) == 0: 
                D.pop(elem)
            else:
                break
        return value
        
    # setup some aliases for pop() and pop_path()
    remove = pop
    remove_path = pop_path
    
    @staticmethod
    def iteritems(D, depth=None):
        stack = [D.iteritems()]
        path  = []
        while len(stack) > 0:
            iterator = stack[-1]
            for key, value in iterator:
                path.append(key)
                if isinstance(value, dict) and (depth is None or len(path) < depth):
                    stack.append(value.iteritems())
                    break
                path.append(value)
                yield tuple(path)
                path.pop()
                path.pop()
            # pop stack if the for loop above has run till the end
            if iterator is stack[-1]:
                stack.pop()
                if len(path) > 0:
                    path.pop()
                    
    @staticmethod
    def copy(D):
        return treedict(D.iteritems())
        
        
# ---------------------------------------------------------
# Useful constants ----------------------------------------
UNDEF = Undefined()
INF   = float("inf")

# ---------------------------------------------------------
# Utility functions  --------------------------------------
def callable_name(callable):
    """Returns the name of a function or method. If the object is callable but does not have a 
    __name__ attribute, it returns str(callable) instead."""
    try:
        return callable.__name__
    except AttributeError:
        return str(callable)
        
def identity_fnc(x):
    return x
    
def rgb_to_str(r, g, b):
    return "#%02x%02x%02x" % (r, g, b)
    
def attrgetter(name):
    def getter(obj):
        return getattr(obj, name)
    getter.__name__ = "attrgetter<%s>" % name
    return getter
    
def xgetattr(obj, location):
    attrs = location.split(".")
    for attr in attrs:
        obj = getattr(obj, attr)
    return obj
    
def xsetattr(obj, location, value):
    attrs = location.split(".")
    for attr in attrs[:-1]:
        obj = getattr(obj, attr)
    setattr(obj, attrs[-1], value)
    
def xdelattr(obj, location):
    attrs = location.split(".")
    for attr in attrs[:-1]:
        obj = getattr(obj, attr)
    delattr(obj, attrs[-1])
    
def is_sorted(iterable, key=identity_fnc):
    iterator = iter(iterable)
    prev_key = key(iterator.next())
    for item in iterator:
        curr_key = key(item)
        if curr_key < prev_key:
            return False
        prev_key = curr_key
    return True
    
def ranking(items, key=identity_fnc):
    """This function produces a ranking for a given group of items. The 'key' argument specifies 
    the comparison key, just like the builtin sorted() function. Items are ranked from highest 
    key (first position) to lowest key (last position). Additionally, if n items are tied for 
    position p, then the next item will receive position p+n."""
    order = sorted([(key(i), i) for i in items], reverse=True)
    rank = dict()
    position = 1
    value = order[0][0]
    tied = 0
    for v, i in order:
        if v == value:
            tied += 1
        elif v < value:
            position += tied
            value = v
            tied = 1
        rank[i] = position
    return rank
    
def equals(a, b, epsilon=sys.float_info.min):
    """A function for comparing floating point numbers in a safe manner, using a tolerance 
    parameter 'epsilon' which allows the function to recognize equality between very close but not 
    exactly equal numbers. This is a useful hack around the loss of precision caused by floating 
    point arithmetics."""
    return abs(a - b) <= epsilon
    
def biased_choice(items, biases, rng=random):
    """Randomly select an element from a list using different probabilities for selecting each
    element. The first argument should be a list (or list-like object) of python objects of any 
    type, and 'biases' should be a list of the same size containing the bias of the item in the 
    first list located at the same index. Biases should be non-negative real numbers of any 
    magnitude (not just in [0, 1], because their relative sizes dictate their associated 
    probability p_i = b_i / sum(b_j for all j))."""
    a = rng.uniform(0.0, sum(biases))
    x = 0.0
    i = 0
    for b in biases:
        x += b
        if x >= a:
            return items[i]
        i += 1
    raise Exception("They came from behind!!!")
    
@contextmanager
def import_path(directory):
    directory = path.abspath(directory)
    sys.path.append(directory)
    yield
    sys.path.remove(directory)
    
def subsets(elements):
    """This function returns a generator which iterates over the subsets of the given iterable."""
    elements = list(elements)
    for size in xrange(len(elements) + 1):
        for subset in _subsets(elements, 0, list(), size):
            yield subset
            
def _subsets(elements, start_idx, subset, remaining):
    if remaining == 0:
        yield subset
    elif start_idx + remaining == len(elements):
        yield subset + elements[start_idx:]
    else:
        new_subset = list(subset)
        new_subset.append(elements[start_idx])
        for full_subset in _subsets(elements, start_idx + 1, new_subset, remaining - 1):
            yield full_subset
        for full_subset in _subsets(elements, start_idx + 1, subset, remaining):
            yield full_subset
            
try:
    # Clock function replacement for unix systems.
    from resource import getrusage, RUSAGE_SELF
    def clock():
        """clock() -> floating point number
        
        Return the CPU time in seconds (user + system) since the start of the
        process. This is done via a call to resource.getrusage(), so it avoids
        the wraparound problems in time.clock()."""
        res = getrusage(RUSAGE_SELF)
        return res[0] + res[1]
except ImportError:
    # For other systems the time module's clock() is okay.
    from time import clock
    